#include <stdio.h>
#include <stdlib.h>
#include <time.h>


void initialisation_robuste_entier(int * e);
/* Preconditions : aucune
   Postconditions : e est initialise par une saisie clavier. En cas de saisie 
   invalide (par exemple "azerty" au lieu d'un nombre), une nouvelle saisie
   est demandee a l'utilisateur. Sortie du programme si l'utilisateur simule
   une fin de fichier (CTRL+D). */


int litFichierEntiers(const char * nomFicher, Tab_Dynamique *t);
/* Preconditions : nomFichier est une chaine de caracteres contenant le nom 
   d'un fichier texte, structure de la facon suivante :
     ------------------------
    |#nblignes: [entier]     |
    |[entier1]               |
    |[entier2]               |
    |[entier3]               |
    |[entier4]               |
    |..etc..                 |
    |[entier(nblignes)]      |
     ------------------------
   adrTab est l'adresse a laquelle est stockee un pointeur sur entier.

   Postconditions : un segment memoire assez grand pour stocker les (nblignes)
   entiers est reserve dans le tas. L'adresse de base de ce tableau est
   memorisee dans *adrTab. Les entiers stockes dans le fichier sont recopies
   dans le tableau. A charge pour le sous-programme appelant de liberer le
   tableau une fois tous les traitements effectues. 

   Resultat : retourne le nombre d'entiers lus (nblignes si tout va bien) */



int ecrireFichierEntiers(const char * nomFichier, Tab_Dynamique * t);
/* Preconditions : nomFichier est une chaine de caracteres contenant le nom 
   d'un fichier texte a creer dans le repertoire courant. tab est un tableau 
   contenant "taille" entiers. 
   Postconditions : un fichier texte nomme comme le contenu de la chaine nomFichier 
   est cree dans le repertoire courant. (Si ce fichier existe deja, son contenu 
   est ecrase). Ce fichier contient une premiere ligne de la forme "#nblignes: [entier]", 
   puis Les entiers contenus dans tab, a raison d'un entier par ligne. 
   Resultat : retourne le nombre d'entiers écrits avec succes. */


void triParSelectionDuMinimum(Tab_Dynamique * t);
/* Preconditions : tab est un tableau contenant "taille" entiers.
   Postconditions : les elements de tab sont ranges dans l'ordre croissant
   a l'aide de l'algorithme de tri par selection du minimum. */


void triParInsertion(int * tab, int taille);
/* Preconditions : tab est un tableau contenant "taille" entiers.
   Postconditions : les elements de tab sont ranges dans l'ordre croissant
   a l'aide de l'algorithme de tri par insertion. */


void triParFusionInterne(int * tab, int taille);
/* Preconditions : tab est un tableau contenant "taille" entiers.
   Postconditions : les elements de tab sont ranges dans l'ordre croissant
   a l'aide de l'algorithme de tri par fusion. */


void triParFusionExterne(const char * nomFic, const char * nomFicSortie);
/* Preconditions : nomFic est une chaine de caracteres contenant le nom 
   d'un fichier texte, structure de la facon suivante :
     ------------------------
    |#nblignes: [entier]     |
    |[entier1]               |
    |[entier2]               |
    |[entier3]               |
    |[entier4]               |
    |..etc..                 |
    |[entier(nblignes)]      |
     ------------------------
   nomFicSortie est le nom d'un fichier texte a creer dans le repertoire
   courant.

   Postconditions : un fichier texte nomme comme la chaine contenue dans 
   nomFicSortie est cree dans le repertoire courant. (Si un fichier de ce
   nom existait deja, il est ecrase). Ce fichier contient les memes entiers
   que le fichier d'entree, mais ceux-ci sont tries dans l'ordre croissant.
   Le tri est externe : on ne charge pas en memoire vive l'ensemble du 
   fichier, et on accede sequentiellement aux elements. 
 */



static void eclatement(const char * nomFicX, int lg, \
		const char * nomFicA, const char * nomFicB);
/* Procedure auxiliaire pour le tri externe par fusion */
/* Precondition : le fichier appele nomFicX contient des monotonies de longueur lg, 
   sauf peut-etre la derniere qui peut etre plus courte
   Postcondition : Les monotonies de nomFicX sont reparties dans des fichiers appeles 
   nomFicA et nomFicB : la premiere monotonie est copiee dans le fichier A, la seconde 
   dans le fichier B, la troisieme dans le A, etc. Si ces fichiers existaient deja, 
   leur contenu est ecrase. Le fichier A peut recueillir une monotonie de plus que le 
   fichier B, et cette derniere monotonie peut etre de longueur inferieure a lg. 
   Si au contraire ficA et ficB recueillent le meme nombre de monotonies, la derniere
   monotonie ecrite dans ficB peut etre de longueur inferieure a lg. */


static void fusionExterne(const char * nomFicA, const char * nomFicB, int lg,\
		   const char * nomFicX, int * nbMonoDansX);
/* Procedure auxiliaire pour le tri externe par fusion */
/* Preconditions : les fichiers appeles nomFicA et nomFicB contiennent des monotonies 
   de longueur lg. FicA peut contenir une monotonie de plus (eventuellement incomplete) 
   que FicB. Si au contraire FicA et FicB contiennent le meme nombre de monotonies, 
   alors la derniere monotonie de FicB peut etre incomplete.
   Postconditions : le fichier appele nomFicX contient nbMonoApres monotonies de 
   longueur 2*lg, la derniere pouvant etre plus courte. Ces monotonies resultent de 
   la fusion 2 a 2 des monotonies de FicA et de FicB. Si FicX existait deja, son ancien 
   contenu est ecrase. */  






int main()
{
  Tab_Dynamique t;

  int algo = -1;
  char nomFic[101];
  char nomFicTrie[111];
  clock_t heureDebut, heureFin;


  /* Saisie du nom de fichier a lire */
  printf("Tapez le nom du fichier a trier (100 caracteres max) :\n");
  scanf("%100s", nomFic);
  sprintf(nomFicTrie, "resultattri-%s", nomFic);


  /* Saisie de l'algorithme de tri a utiliser */
  do
    {
      printf("\nChoisissez l'algorithme de tri a executer : \n");
      printf("0 : selection du minimum\n");
      printf("1 : insertion\n");
      printf("2 : fusion (interne)\n");
      printf("3 : fusion (externe)\n");
      initialisation_robuste_entier(&algo);
    }
  while ((algo < 0) || (algo > 3)); 


  heureDebut = clock();
  if (algo < 3)
    {
      /* Ecrivez ici l'instruction pour lire le fichier, c'est-a-dire le charger dans le tableau */
      litFichierEntiers(nomFic, &t);
      switch(algo)
        {
        case 0: {triParSelectionDuMinimum(monTab, taille); break;}
        case 1: {triParInsertion(monTab, taille); break;}
        case 2: {triParFusionInterne(monTab, taille); break;}
        }

      /* Ecrivez ici l'instruction pour ecrire le fichier trie */
      ecrireFichierEntiers(nomFicTrie, &t);
      
      free(monTab);
    }
  else
    {
      triParFusionExterne(nomFic, nomFicTrie);
    }

  heureFin = clock();
  

  /* Afficher le temps ecoule */
  printf("Temps d'execution: %f secondes.\n", ((float)(heureFin - heureDebut))/CLOCKS_PER_SEC);


  exit(EXIT_SUCCESS);
}





int litFichierEntiers(const char * nomFichier, Tab_Dynamique *t)
{
	int e,valret;
	FILE * monFic;
	char c;
	monFic = fopen(nomFichier,"r");
	
	if(monFic == NULL)
	{
		printf("Impossible d’ouvrir le fichier\n");
		exit(EXIT_FAILURE);	
	}
	/* premiere ligne ! */	
	valret = fscanf(monFic,"%s",&c);
	if(valret != 1)
	{
		printf("Fin de fichier ou erreur de lecture \n ");
		exit(EXIT_FAILURE);	
	}
	/* premier int ! */
	valret = fscanf(monFic, "%d", &e);
	if(valret != 1)
	{
		printf("Fin de fichier ou erreur de lecture \n ");
		exit(EXIT_FAILURE);	
	}
	/* Copie des entiers dans le tableau. */
	valret = fscanf(monFic, "%d", &e);	
	while(valret == 1)
	{	
		ajouteElement( T, e);
		valret = fscanf(monFic, "%d", &e);	
		
	}
	fclose(monFic);
}




void ecrireFichierEntiers(const char * nomFichier, Tab_Dynamique * t)
{
	FILE * monFic;
	int i;
	monFic=fopen(nomFichier,"w");
	if(monFic==NULL)
	{
		printf("ouverture impossible\n");
		exit(EXIT_FAILURE);
	}
	for(i=0; i < t->derniere_position ; i++ )
	{	
		fprintf(monFic,"%d\n",t->ad[i]);
	}
	fclose(monFic);
}




void initialisation_robuste_entier(int * e) 
{
  int valretour ;	
  char c;
  valretour = scanf("%d", e); 
  while (valretour != 1) 
    {
      if(valretour == EOF)
	{
	  /* CTRL+D sur un buffer vide */
	  printf("Initialisation impossible 1 (fin de fichier)\n");
	  exit(EXIT_FAILURE);
	}

      /* printf("Caractere invalide, je vide le buffer... \n"); */

      do 
	{
	  valretour = scanf("%c",&c);
	}
      while((c!='\n') && (valretour != EOF));

      if(valretour == EOF)
	{
	  /* le buffer contenait des caractères invalides puis CTRL+D */
	  printf("Initialisation impossible 2 (fin de fichier)\n");
	  exit(EXIT_FAILURE);
	}

      printf("Recommencez votre saisie : \n");
      valretour = scanf("%d", e);
    }
}





void triParSelectionDuMinimum(Tab_Dynamique * t)
{
  int i, j;
  int indmin;
  int min;

  for(i = 0; i < t->derniere_position - 1; i++)
    {
      indmin = i;
      for(j = i+1; j < t->derniere_position; j++)
        {
          if (t->ad[j] < t->ad[indmin])
            {
              indmin = j;
            }
        }
      min =  t->ad[indmin];
      t->ad[indmin] = t->ad[i];
      t->ad[i] = min;
    }
}







void triParInsertion(Tab_Dynamique * t)
{
  int i, j;
  int elt_a_placer;
  
  for(j = 1; j < t->derniere_position; j++)
    {
      elt_a_placer = t->ad[j];
      i = j - 1;
      while ((i >= 0) && ( t->ad[i] > elt_a_placer))
        {
        	t->ad[i+1] = t->ad[i];
          i--;
        }
     	t->ad[i+1] = elt_a_placer;
    }
}



/* On fait le traitement a moitie sur place. Lors de la fusion, 
   on effectue une copie de la premiere monotonie en memoire temporaire 
   (on peut faire une copie des deux monotonies, mais ce n'est pas necessaire). 
   Ainsi, lors de la fusion, on a pas besoin de decaler les donnees, on copie 
   simplement un element de la premiere liste (depuis la memoire temporaire) ou 
   de la deuxieme liste (qui est gardee sur place). */
void triParFusionInterne(Tab_Dynamique *t)
{
  int * tmp;
  int debutMono1, debutMono2;
  int nbMono1traites, nbMono2traites;
  int lgMono = 1;
  int i,j,k;

  while (lgMono < taille)
    {
      tmp = (int *) malloc(lgMono * sizeof(int));
      debutMono1 = 0;
      debutMono2 = debutMono1 + lgMono;

      while (debutMono2 < t->derniere_position) /* tant qu'on a une paire de monotonies a fusionner */ 
        {
          k = debutMono1;  /* index dans tab */
          i = 0;           /* index dans tmp */
        
          /* On recopie la premiere monotonie dans tmp */
          /* (On est sur qu'elle est complete, car si on est rentre dans le while,
             c'est que debutMono2 < taille) */         

         while(k < debutMono2)
	{
		tmp[i] = t->ad[k];
		i++;
		k++;
	}
          
          /* On fusionne les deux monotonies */
          /* Attention, la seconde peut être incomplete */
          i = 0;             /* index dans tmp, monotonie 1 */
          j = debutMono2;    /* index dans tab, monotonie 2 */
          k = debutMono1;    /* index dans tab, monotonie fusionnee */
          nbMono1traites = nbMono2traites = 0;
          while((nbMono1traites < lgMono) && (nbMono2traites < lgMono) && (j < taille)) 
            /* tant qu'aucune monotonie n'est epuisee */
            {
              if(tmp[i] <= t->ad[j])
			{
				t->ad[k] = tmp[i];
				i++;
				k++;
				nbMono1traites++;
			}
			else
			{
				t->ad[k] = t->ad[j];
				j++;
			 	k++;
			 	nbMono2traites++;
			 }
            }
          


          if ((nbMono2traites == lgMono) || (j == taille))
            {
              /* On a epuise la seconde monotonie, il reste a recopier la
                 premiere */
              
               while(nbMono1traites < lgMono)
      		{
       			t->ad[k] = tmp[i];
			i++;
			k++;
			nbMono1traites++;
       		}
            }


          /* Dans le cas ou on est sorti du while parce que la monotonie 1 
             est epuisee, il n'y a rien a faire, les elements de la monotonie 2 
             sont deja en place */

          /* On passe a la paire de monotonies suivante */
          debutMono1 += (2*lgMono);
          debutMono2 += (2*lgMono);
        }
      free(tmp);
      lgMono *= 2;
    }
}







void triParFusionExterne(const char * nomFic, const char * nomFicSortie)
{

  int nbMonotonies;
  int longueur = 1;
  char nomA[] = "fichierAnnexeA.txt";
  char nomB[] = "fichierAnnexeB.txt";
  FILE * fic, *ficSortie;
  int e;
  
  /* On cree une copie du fichier, sur laquelle l'algo va travailler */
  /* On enleve la ligne avec le nombre de lignes pour simplifier 
     les procedures eclatement et fusionExterne */

  fic = fopen(nomFic, "r");
  if (fic == NULL)
    {
      fprintf(stderr, "Erreur, impossible d'ouvrir le fichier %s\n", nomFic);
      return;
    }
  
  ficSortie = fopen(nomFicSortie, "w");
  if (ficSortie == NULL)
    {
      fprintf(stderr, "Erreur, impossible d'ouvrir le fichier %s\n", nomFic);
      return;
    }

  if (fscanf(fic, "#nblignes: %d", &e) != 1) 
    {
      fprintf(stderr, "Erreur de format\n");
      return;
    }

  while(fscanf(fic, "%d", &e) == 1)
    {
      fprintf(ficSortie, "%d\n", e);
    }

  fclose(fic);
  fclose(ficSortie);

  do
    {
      eclatement(nomFicSortie, longueur, nomA, nomB);
      fusionExterne(nomA, nomB, longueur, nomFicSortie, &nbMonotonies);
      longueur *= 2;
    } 
  while (nbMonotonies > 1);

  
}



static void eclatement(const char * nomFicX, int lg, \
		const char * nomFicA, const char * nomFicB)
{
  /* A completer */
}






static void fusionExterne(const char * nomFicA, const char * nomFicB, int lg,\
                          const char * nomFicX, int * nbMonoDansX)
{
  /* Completer en suivant le squelette ci-dessous */

  FILE * ficA, * ficB, * ficX;
  int nbAtraites, nbBtraites; 
  double e1, e2;

  /* Ouverture de trois fichiers : ficA et ficB en lecture, ficX en ecriture */
  /* (penser a faire quitter le programme si l'ouverture echoue */
  







  /* Boucle tant qu'il reste quelque chose dans le fichier 2 (= tant qu'il
     reste des monotonies a fusionner 2 a 2) */
  /* (Rmq : s'il reste des monotonies dans le fichier 2, alors il en reste 
     dans le fichier 1, et celle dans le fichier 1 est de longueur lg) */

  while( 1 < 2 /* a remplacer par la vraie condition !! */ ) 
    {

      /* initialiser les compteurs nbAtraites et nbTraites */
 

      /* lire l'element suivant dans ficA pour initialiser e1*/


      /* boucle de fusion des deux monotonies courantes */
      do
	{	

          /* si e1 <= e2, on ecrit e1 dans ficX, on incremente nbAtraites,
             et, si c'est nécessaire (si on n'a pas traite toute la 
             monotonie A), on met a jour e1 */




          /* sinon, on ecrit e2 dans ficX, on incremente nbBtraites, et,
             si necessaire, on met a jour e2. Attention au cas d'une 
             monotonie finale incomplete dans ficB. */






	} while ( 1 < 2 /* a remplacer par la vraie condition !! */ ); 
      /* (tant qu'il reste des elements a traiter dans la monotonie A et
         dans la monotonie B) */
                                 


      /* si la monotonie A a ete completement traitee, il reste a ecrire
         telle quelle dans ficX la fin eventuelle de la monotonie B. Attention,
         au cas d'une monotonie finale incomplete dans ficB. */


      
      /* sinon, c'est que c'est l'inverse : B a ete completement traitee, 
         il reste a ecrire telle quelle dans ficX la fin eventuelle de la
         monotonie A. */



      /* avant de passer aux 2 monotonies suivantes, on incremente nbMonoDansX */


    }


  /* Enfin, n'oublions pas l'eventuelle monotonie supplementaire de ficA,
     qui est a recopier telle quelle dans ficX */



  /* Fermeture des trois fichiers */



}
